#include <iostream>
#include <cassert>

using namespace std;

// todo 类似插入排序优化,将交换改成赋值操作
template<typename Item>
class MaxHeap{
	private:
		Item* data;		// 数组指针
		int count;		// 堆里面有多少成员变量
		int capacity;	// 堆最大容量

		// 先放入最后一个位置,然后向上移
		void shiftUp(int k){
			while(k > 1 && data[k/2] < data[k]){	// 边界
				swap(data[k/2], data[k]);
				k /= 2;					// 更新k
			}
		}

		// 从上向下交换
		void shiftDown(int k){
			// 判断是否有孩子->有左孩子
			while(2*k <= count){
				// 此轮循环,data[k]和data[j] 交换位置
				int j = 2*k;
				if(j+1 <= count && data[j+1] > data[j])	// 和右孩子交换位置
					j += 1;
				if(data[k] >= data[j])					// 大于两个孩子,j是取最大值
					break;								// 不交换，直接退出
				swap(data[k], data[j]);
				k = j;									// 赋值给k,继续向下移动
			}
		}
	public:
		MaxHeap(int capacity){
			data = new Item[capacity + 1];	// 索引从1开始
			count = 0;
			this->capacity = capacity;
		}

		MaxHeap(Item arr[], int n){
			data = new Item[n + 1];
			capacity = n;
			for(int i = 0;i < n; ++i)
				data[i + 1] = arr[i];
			count = n;
			for(int i = count / 2; i >= 1; --i)
				shiftDown(i);
		}

		~MaxHeap(){							// 析构函数
			delete [] data;
		}

		int size(){
			return count;
		}

		bool isEmpty(){
			return count == 0;
		}
		
		// 添加元素
		void insert(Item item){			
			assert(count + 1 <= capacity);
			data[count + 1] = item;		// 只开辟一次空间,存在数组越界
			count ++;
			shiftUp(count);				// 最后一个元素上移
		}

		// 取出最大值
		Item extractMax(){
			assert(count > 0);	// 堆不为空
			Item ret = data[1];	// 取出索引为1元素

			swap(data[1], data[count]);	// 将第一个元素和最后一个元素互换
			count--;
			shiftDown(1);				// 第一个元素下移
			return ret;
		}

		void toString(){
			for(int i = 1;i <= count; ++i)
				cout << data[i] << "\t" ;
			cout << endl;
		}
	
};
